package com.tgy.algorithm.base._bfprt算法;

import java.util.Arrays;

/**
 * 找出第k小第数
 */
public class _获取一个无序数组的第k个数_快速排序 {

    public static int findKOrder(int[] nums, int k) {

        if (nums == null || nums.length == 0) {
            return -1;
        }

        int len = nums.length;
        if (k >= len) {
            return -1;
        }

        return doFindOrder(nums,0,len-1,k-1);
    }

    /*
     *   2 到 5
     */
    public static int doFindOrder(int[] nums,int left, int right, int k) {

        if (left >= right) {
            return nums[left];
        }

        int[] middle = findMiddle(nums, left, right);

        int leftEqual = middle[0];
        int rightEqal = middle[1];

        if (k >= leftEqual && k <= rightEqal) {
            return nums[leftEqual];
        }else if(k < leftEqual) {
            return doFindOrder(nums,left,leftEqual -1,k);
        }else {
            return doFindOrder(nums,rightEqal+1,right,k);
        }
    }

    public static int[] findMiddle(int[] nums,int left,int right) {

        int[] rets = new int[2];
        int randomIndex = left + (int) (Math.random() * (right - left + 1));
        // 随机放一个到right位置
        swap(nums,randomIndex,right);
        int leftIndex = left - 1;
        int rightIndex = right - 1;
        int index = left;
        int povit = nums[right];
        while (index <= rightIndex) {
            int value = nums[index];
            if (value < povit) {
                if (leftIndex + 1 != index) {
                    swap(nums,leftIndex+1,index);
                }
                leftIndex++;
                index++;
            }else if (value == povit) {
                index++;
            }else {
                swap(nums,rightIndex,index);
                rightIndex--;
            }
        }

        swap(nums,rightIndex+1,right);
        rets[0] = leftIndex+1;
        rets[1] = rightIndex+1;
        return rets;
    }

    public static void swap(int[] nums,int one, int two) {
        int tmp = nums[one];
        nums[one] = nums[two];
        nums[two] = tmp;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{3,2,4,5,1,4,3};
        int[] middles = findMiddle(nums, 0, nums.length - 1);
//        System.out.println(Arrays.toString(middles));
//        System.out.println(Arrays.toString(nums));
        int[] newNums = Arrays.copyOf(nums, nums.length);
        int val = findKOrder(nums, 2);
        System.out.println(val);
        Arrays.sort(newNums);
        System.out.println(Arrays.toString(newNums));
    }
}
